Reed-Solomon code (referred to as RS code hereinafter) is a type of maximum distance separable code, which now has been widely used in storage and communication systems. The current methods for encoding RS codes generally include polynomial division, matrix-vector multiplication-based and fast Fourier transform-based algorithms.
Wherein, with respect to the RS encoding based on the polynomial division, the generator polynomial is defined as: g(X)=(X−a)(X−a2) . . . (X−a3), where g(X) is the generator polynomial, a is the primitive element of the finite field GF(2m), and s is the number of redundant symbols. Let o=[o1, o2 . . . ok] denote k message symbols, and then the polynomial for message symbols is defined as o(X)=o1o2X+. . . +okXk−1, and the redundant symbol polynomial r(X) can be obtained by the formula: r(X)=o(X)Xs (mod g(X)), where r(X) is the remainder polynomial. However, the encoding based on polynomial division requires around sk finite field additions and sk finite field multiplications, and thus, the computational complexity is O(sk×Mq), where Mq is the complexity of a multiplication/addition in a finite field.
For RS encoding based on matrix-vector multiplication, it requires a given generator matrix G=[P I] where I is a k×k identity matrix, P is a given k×s matrix, s denotes the number of redundant symbols, and k denotes the number of message symbols. The codeword is defined as c=oG=o[P I]=[oP o]. In the formula, c is the codeword, o is the message symbol, and oP is a vector-matrix multiplication, the result vector of which consists of s check bits. The complexity of computing oP is the same as that of the polynomial division described above, and both of them are large.
For the RS encoding based on the fast Fourier transform, the constant term of such algorithms is relatively large, so it is not suitable for short RS codes.
For short RS codes, some researchers proposed the method of optimizing matrix-vector multiplication. For example, the Cauchy matrix is used to replace the Vandermonde matrix, and the finite field multiplication in the encoding process can be converted into exclusive OR (XOR) operations. However, these techniques do not change the structure of the matrix-vector multiplication, so the degree of optimization is limited and the computational complexity is still huge.
In order to reduce the amount of computation, some researchers proposed some other codes. These other codes are not RS codes, but both those codes and the RS codes belong to MDS codes. For example, when the number of redundant symbols s=2, there are EvenOdd, X-Code, RDP (Row-Diagonal Parity), P-Code, and so on. When s=3, there are Star Code, RTP (RAID triple parity), and so on. However, such methods can only correspond to the codes with a small number of redundant symbols, such as s=2, 3, and when s=3, those codes require at least three finite field additions.
It can be seen that, in the prior art, although there are encoding methods for reducing RS codes with a small number of redundancies (i.e., the short RS codes), the reduction of the computational complexity is limited and the computation speed is very slow.